package offer;

public class offerII_0070 {
    public int singleNonDuplicate(int[] nums) {
        int len=nums.length;
        return nums[search(nums,0,len-1)];
    }
    public int search(int[] nums,int left,int right){
        if(left==right) return left;
        int mid=left+(right-left)/2;
        if(nums[mid]!=nums[mid-1]&&nums[mid]!=nums[mid+1]) return mid;
        if(mid%2==0){
            if(nums[mid]==nums[mid+1]) return search(nums,mid+2,right);
            else return search(nums,left,mid-2);
        }
        else{
            if(nums[mid]==nums[mid-1]) return search(nums,mid+1,right);
            else return search(nums,left,mid-1);
        }
    }
}
